package developer.算法.滑动窗口.字符串异位词;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author zhangyongkang
 * @time 2025/3/13 14:37
 * @description 给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，
 * 返回这些子串的起始索引。不考虑答案输出的顺序。
 * <p>
 * 示例 1:
 * <p>
 * 输入: s = "cbaebabacd", p = "abc"
 * 输出: [0,6]
 * 解释:
 * 起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
 * 起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
 * 示例 2:
 * <p>
 * 输入: s = "abab", p = "ab"
 * 输出: [0,1,2]
 * 解释:
 * 起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
 * 起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
 * 起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
 * <p>
 * <p>
 * 提示:
 * <p>
 * 1 <= s.length, p.length <= 3 * 104
 * s 和 p 仅包含小写字母
 */
public class ZifuchuanSolution {
    public static void main(String[] args) {
//        List<Integer> sss = findAnagrams("cbaebabacd", "abc");
        List<Integer> sss = findAnagrams("abab", "ab");
        System.out.println(sss.toString());
    }

    public static List<Integer> findAnagrams(String s, String p) {
        char[] charArray = p.toCharArray();
        Arrays.sort(charArray);

        char[] aArray = s.toCharArray();
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < aArray.length; i++) {
            if (i > aArray.length - charArray.length) {
                continue;
            }
            char[] cache = new char[charArray.length];
            int cacheIndex = 0;
            for (int j = i; j < i + charArray.length; j++) {
                cache[cacheIndex++] = aArray[j];
            }
            Arrays.sort(cache);
            if (Arrays.equals(cache, charArray)) {
                result.add(i);
            }
        }
        return result;
    }


    //官方题解

    /**
     * 根据题目要求，我们需要在字符串 s 寻找字符串 p 的异位词
     * 。因为字符串 p 的异位词的长度一定与字符串 p 的长度相同
     * ，所以我们可以在字符串 s 中构造一个长度为与字符串 p 的长度相同的滑动窗口，并在滑动中维护窗口中每种字母的数量；当窗口中每种字母的数量与字符串 p 中每种字母的数量相同时，
     * 则说明当前窗口为字符串 p 的异位词。
     * <p>
     * 算法
     * <p>
     * 在算法的实现中，我们可以使用数组来存储字符串 p 和滑动窗口中每种字母的数量。
     * <p>
     * 细节
     * <p>
     * 当字符串 s 的长度小于字符串 p 的长度时，字符串 s 中一定不存在字符串 p 的异位词。但是因为字符串 s 中无法构造长度与字符串 p 的长度相同的窗口，所以这种情况需要单独处理。
     * <p>
     * 作者：力扣官方题解
     * 链接：https://leetcode.cn/problems/find-all-anagrams-in-a-string/solutions/1123971/zhao-dao-zi-fu-chuan-zhong-suo-you-zi-mu-xzin/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     *
     * @param s
     * @param p
     * @return
     */
    public static List<Integer> findAnagrams_official(String s, String p) {
        int sLen = s.length(), pLen = p.length();

        if (sLen < pLen) {
            return new ArrayList<Integer>();
        }

        List<Integer> ans = new ArrayList<Integer>();
        int[] count = new int[26];
        for (int i = 0; i < pLen; ++i) {
            ++count[s.charAt(i) - 'a'];
            --count[p.charAt(i) - 'a'];
        }

        int differ = 0;
        for (int j = 0; j < 26; ++j) {
            if (count[j] != 0) {
                ++differ;
            }
        }

        if (differ == 0) {
            ans.add(0);
        }

        for (int i = 0; i < sLen - pLen; ++i) {
            if (count[s.charAt(i) - 'a'] == 1) {  // 窗口中字母 s[i] 的数量与字符串 p 中的数量从不同变得相同
                --differ;
            } else if (count[s.charAt(i) - 'a'] == 0) {  // 窗口中字母 s[i] 的数量与字符串 p 中的数量从相同变得不同
                ++differ;
            }
            --count[s.charAt(i) - 'a'];

            if (count[s.charAt(i + pLen) - 'a'] == -1) {  // 窗口中字母 s[i+pLen] 的数量与字符串 p 中的数量从不同变得相同
                --differ;
            } else if (count[s.charAt(i + pLen) - 'a'] == 0) {  // 窗口中字母 s[i+pLen] 的数量与字符串 p 中的数量从相同变得不同
                ++differ;
            }
            ++count[s.charAt(i + pLen) - 'a'];

            if (differ == 0) {
                ans.add(i + 1);
            }
        }

        return ans;
    }

}
